/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package csm.uttils.generics;

import csm.uttils.Operations;
import java.io.Serializable;


    /**
 *
 * @author Carlos S. Moreno
 */
public class hashChart<E> implements Serializable {

    private E[] elementos;
    private byte[] state;
    private int count;


    /**
     * Devuelve la cantidad de elementos almacenados en la talba
     * @return Cantidad de elementos
     */
    public int getCount()
    {
        return count;
    }
    /**
     * Devuelve la clase de los elementos almacenados en la tabla
     * @return Clase de los elementos almacenados
     * @exception NoSuchElementException Si la tabla no contiene elementos
     */
    public Class getElementsClass()
    {
        if (count == 0) throw new java.util.NoSuchElementException("No hay elementos en la lista");
        return getFirst().getClass();
    }//Fin getElementsClass

    private E getFirst()
    {
        for(int i = 0; i <= elementos.length; i++)
        {
            if(state[i]==1)return elementos[i];
        }
        throw new java.util.NoSuchElementException("No hay elementos en la lista");
    }

    /**
     * Constructor por defecto
     */
    public hashChart()
    { this(7);}
    
    /**
     * Constructor con parametros
     * @param n tamaño de la tabla
     */
    public hashChart(int n){
        arrayLength(n);
    }

    private void arrayLength(int n) {
        elementos = (E[]) new Object[n];
        state = new byte[n];
    }

    /**
     * Indica si la tabla debe redefinir su tamaño o no
     * @return True, si ebe ser redefinida
     */
    private boolean needResize(){
        return count / elementos.length >= 3/4;
    }

    private void reDim()
    {
        Object[] temp = elementos;
            //Busco el nuevo tamaño
            int num = (int) Math.ceil((double)elementos.length * 1.5d);
            arrayLength(Operations.nextPrime(num));

            count = 0;

        // recorremos la vieja tabla, para extraer uno a uno los objetos que contenía...
        for (int j = 0; j < temp.length; j++) {
            if (temp[j] != null) {
                add((E) temp[j]);
            }
        }
    }


    /**
     * Busca un lugar adecuado para el elemento nuevo y lo agrega
     * @param info
     * @return
     */
    private boolean add(E info)
    {
        // ... luego dispersamos la clave...
        int y = hashPosition(info.hashCode());
        int posicion = y;
        int posicionTumba = -1;
        int posActual = 0;
        int n = 0;
        while (n <= state.length && state[posActual = position(posicion + (n * n))] != 0) { //0 vacio, 1 ocupado, 2 tumba

            if (elementos[posActual] != null && elementos[posActual].hashCode() == info.hashCode()) {
                return false;
            }
            if (state[posActual] == 2 && posicionTumba == -1) {
                posicionTumba = posActual;
            }
            n++;
        }
        if (posicionTumba != -1) {
            elementos[posicionTumba] = info;
            state[posicionTumba] = 1;
        } else {
            elementos[posActual] = info;
            state[posActual] = 1;
        }
        count++;
        return true;
    }

    /**
     * Agrega un elemento a la tabla, con todo el
     * procedimiento que ello implica
     * @param info Elemento a agregar
     */
    public boolean put(E info)
    {
        //Si el info es nulo, no se agrega, y lanza una exception
        if (null == info) throw new NullPointerException();

        if(needResize())reDim();

        if (get(info) != null) return false;
        else return add(info);

       /* if (get(info) != null) {return false;}


            // ... y finalmente pedimos a la lista que corresponda que haga la inserción
            return add(info);
        }
        return false;*/
    }

    /**
     * Permite tratar el array como infinito
     * adaptando el valor del indice
     * @param x
     * @return
     */
    private int position(int x) {
        if (x >= state.length) {
            x = (x % state.length);
        }
        if (x < 0) {
            x = -1 * x;
        }
        return x;
    }


    /**
     * Busca un Objeto en el array y devuelve su posicion
     * @param info
     * @return
     */
    private int searchPosition(E info) {
        int posicion = hashPosition(info.hashCode());
        int n = 0;
        int posActual;
        while (state[posActual = position(posicion + (n * n))] != 0 && n <= state.length) {
            if (elementos[posActual] != null && elementos[posActual].hashCode() == info.hashCode()) {
                return posActual;
            }
            n++;
        }
        return -1;
    }

    /**
     * Busca el objeto info en la tabla, y retorna la dirección del objeto que está en la tabla
     * y coincida con info, o null si info no existía en la tabla o no era de la misma clase que el
     * contenido de la tabla.
     * @param info el objeto a buscar.
     * @return la dirección del objeto que coincide con info en la tabla, o null si no existía.
     */
    public E get(E info) {

        if (info != null) {
            int pos = searchPosition(info);
            if (pos != -1) {
                return (E) elementos[pos];
            }
        }
        return null;
    }

/**
     * Posision hash que le corresponde en la tabla
     * @param k codigo hash del elemento
     * @return posision que le corresponde al elemento
     */
    private int hashPosition(int k)
    {
        return k%elementos.length;
    }

    /**
     * Elimina el objeto info de la tabla. No hace nada si info no es de la misma clase que los
     * objetos que ya estaban en la tabla, o si info no estaba en la tabla.
     * @param info el objeto a eliminar.
     */
    public boolean remove(E info) {

        if (info != null) {
            int pos = searchPosition(info);
            if (pos != -1) {
                state[pos] = 2;
                elementos[pos] = null;
                count--;
                return true;
            }
        }
        return false;
    }

    /**
     * Comprueba si info está en la tabla y retorna true en ese caso, o retorna false si info
     * @param info el objeto a buscar.
     * @return true si info está en la tabla.
     */
    public boolean contains(E info) {
        // si la tabla esta vacia no hace nada...
        if (info != null) {
            if (searchPosition(info) != -1) {
                return true;
            }
        }
        return false;
    }

    /**
     * Devuelve la tabla en formato de un array
     * @return Array con los elementos de la tabla
     */
    public E[] toArray()
    {
        E[] arreglo = (E[])new Object[count];
        if (count == 0) return (E[])new Object[0];

        int indice = 0;
        for (int i = 0; i < elementos.length; i++)
        {
            if (state[i]==1)
            {
                arreglo[indice]=elementos[i];
                if(indice==count)return arreglo;
                indice++;
            }

        }
        return arreglo;
    }

}
